class Solution {
public:
    struct cmp
    {
        bool operator()(ListNode* l1,ListNode* l2)
        {
            return l1->val>l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
      //小堆
      priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
      //将所有链表的头结点入堆
      for(auto e:lists)
      if(e)
      heap.push(e);
      
      ListNode* head=new ListNode(0);
      ListNode* tail=head;

      while(!heap.empty())
      {
        ListNode* node=heap.top();
        heap.pop();
        tail->next=node;
        tail=tail->next;
        if(node->next)
        heap.push(node->next);
      }
      tail=head->next;
      delete head;
      return tail;
    }
};




class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //利用归并排序的思想
        return MergeList(lists,0,lists.size()-1);
    }

    ListNode* MergeList(vector<ListNode*>& lists,int begin,int end)
    {
        if(begin>end)
        return nullptr;
        if(begin==end)
        return lists[begin];
        int mid=(begin+end)/2;

        ListNode* l1=MergeList(lists,begin,mid);
        ListNode* l2=MergeList(lists,mid+1,end);

        //合并两个有序链表
        return MergeTwoList(l1,l2);
    }

    ListNode* MergeTwoList(ListNode* l1,ListNode* l2)
    {
        if(l1==nullptr)
        return l2;
        if(l2==nullptr)
        return l1;

        ListNode* head=new ListNode(0);
        ListNode* tail=head;
        ListNode* cur1=l1,*cur2=l2;
        while(cur1&&cur2)
        {
            if(cur1->val<cur2->val)
            {
                tail->next=cur1;
                tail=tail->next;
                cur1=cur1->next;
            }
            else
            {
                tail->next=cur2;
                tail=tail->next;
                cur2=cur2->next;
            }
        }
        if(cur1)
        tail->next=cur1;
        if(cur2)
        tail->next=cur2;
      
        tail=head->next;
        delete head;
        return tail;
    }
};